COMMENT ⊗   VALID 00004 PAGES
C REC  PAGE   DESCRIPTION
C00001 00001
C00002 00002	\section{Simple list recursion.}
C00012 00003	\section{Simple S-expression recursion.}
C00022 00004	\section{Other structural recursions.}
C00028 ENDMK
C⊗;
\section{Simple list recursion.}
\sectlab{listrec}
	About the simplest form of recursion in LISP occurs when one
of the arguments is a list, the result is immediate when the argument
is null, and otherwise we need only know the result for the d-part of
that argument.  Several of the functions defined in Chapter \chapref{READIN}
are of this form.
Consider, for example, $u\ast v$, the result of /append\//ing
the list /u/ to the list /v/. 
The result is immediate for the case $\qn /u/$ and
otherwise depends on the result for $\qd /u/$.  Thus, we have
\beginfundef
\funlab{fcnappend1}
\vbox{
\hbox{\hskip0\unit $/append/[/u/, /v\//] ← \qif  \qn /u/ \qthen  /v/ \qelse 
 \qa /u/ \qcons  [\qd /u/ * /v\//]$}
}
\endfundef

Notice that if we had tried to recur on /v\// rather than on /u\//
we would not have been successful.  The result would be immediate for
$\qn /v/$, but $/u/*/v/$ cannot be constructed in any direct way from 
$/u/*\qd/v/$.
Often a function is easily defined by a recursion on one of its
arguments and not by recursions on others.

Another example is the function /member\// that tests for membership in
a list.  If the list is empty then the answer is \qNIL\ otherwise
either the element we are searching for is the first thing on the
list, or it is in the rest of the list.  This reasoning gives rise
to the recursive definition
\beginfundef
\vbox{
\hbox{\hskip0\unit $/member/[/x/, /u\//] ← $}
\hbox{\hskip4\unit $    \qif  \qn /u/ \qthen  \qNIL  \qelse  /x/ \qequal 
\qa /u/ \qor /member/[/x/, \qd /u\//]$}
}
\endfundef
The reader should observe that this definition is equivalent
∞to that given by (funref{member}) using only propositional operations.

	The function /reverse/ is another example of simple list recursion.
\beginfundef
\vbox{
\hbox{\hskip0\unit $/reverse/ /u/ ← \qif  \qn /u/ \qthen  \qNIL  \qelse 
 /reverse/ \qd /u/ * <\qa /u/>$}
}
\endfundef

This straightforward definition of /reverse/ involves /append\//ing
the /reverse/ of the rest of the list to the list containing only
the first element of the list.  

	As with recursive definition of numerical functions we see that
simple list recursion parallels the description of the domain of lists
which says that a list is either \qNIL\ or it is the result of /cons\//ing an 
S-expression onto a ``smaller'' list.   
We can give recursion schemas for list recursion analagous to
those for numerical functions.   
In general, the recursive definition of a function on lists must
take into account the fact that we have not one ``successor'' of a given
list, but one for each possible S-expression.
For example ``primitive list recursion'' without parameters has the form
\beginfundef
\funlab{eqnlpr1}
\vbox{
\hbox{\hskip0\unit $/f/ /u/ ← \qif  \qn /u/ \qthen  /g0/   \qelse 
 /h/[\qa /u/, \qd /u/, /f/[\qd /u\//]]$}
}
\endfundef

Taking $g0 = \qNIL$ and $h[x,v,w]= w * [x \qcons \qNIL]$ we get the definition
of /reverse/ given above (\funref{reverse1}).
If we mix numerical and list computation  taking $g0=0$ and $h[x,u,n]=n+1$
we get
\beginfundef
\funlab{fcnlength}
\vbox{
\hbox{\hskip0\unit $/length/ /u/ ← \qif  \qn /u/ \qthen  0 \qelse  /add1/ 
/length/ \qd /u/$}
}
\endfundef

The function /last\// which computes the last element of a list is another example.  
\beginfundef
\funlab{fcnlast}
\vbox{
\hbox{\hskip0\unit $/last/ /u/ ← \qif  \qn \qd /u/ \qthen  \qa /u/ \qelse 
 /last/ \qd /u/$}
}
\endfundef


In order to fit the schema exactly the above definition needs to be patched
somewhat.  See if you can figure out what must be done and what
the ``given'' function /h\// should be.  

The schema for primitive list recursion with parameters (only one parameter shown)
is
\beginfundef
\funlab{eqnlpr2}
\vbox{
\hbox{\hskip0\unit $/f/[/u/,/x\//] ← \qif  \qn /u/ \qthen  /g/[/x\//] \qelse 
 /h/[\qa /u/, \qd /u/, /f/[\qd /u/,/x\//]]$}
}
\endfundef

/append\// \eqref{append1}, /member\// \eqref{member1} and /assoc\// \eqref{assoc}
are examples of this form of definition.   
Allowing a given function of the arguments to occur in the parameter position
in the recursive call on /f\// we obtain the schema
\beginfundef
\funlab{eqnlpr3}
\vbox{
\hbox{\hskip0\unit $/f/[/u/,/x\//] ← \qif  \qn /u/ \qthen  /g/[/x\//] \qelse 
 /h/[\qa /u/, \qd /u/, /f/[\qd /u/,/j/[\qa /u/,\qd /u/, /x\//]]]$}
}
\endfundef

The definition of /reverse\//
(\eqref{reverse}) in terms of the basic /cons\// operation, 
itself and an auxiliary variable has this form.

	The simple recursion on lists without parameters simply proceeds through
a list gathering results to be used in constructing the answer, but provides no
access to information previously obtained.  When we allow parameters to be
carried along the information can be passed down the list as well as results
being passed back up.  The appropriate mixing of control structure and
information passing is often the key to solving a programming problem.
We shall see in a later sections how one can sometimes solve the two
aspects of the problem separately and then piece together the results.

	The function /alt\// (\funref{alt}) which returns a list of alternate
elements of a list is also based on list recursion, however the form of the
recursion is different.
Here the base
cases are the empty list and the list containing one element.  In the
general case we use the result for $\qdd /u/$ to compute the result for /u/.  
This is analogous to the ``course of values'' recursion on numbers 
\funref{pr4}.

	The above schemas, like their numerical counterparts yield definitions
of total functions (assuming that the given functions are total).
The most general form of list recursion is the same as that for numerical
recursion \funref{prec}.  
In the case of pure list recursion we build the term on the
right hand side from basic list functions and expect the arguments to be lists.
As we have seen above we often mix computation involving lists, numbers and
S-expression in general.
Also, as with numerical recursion, recursive definition of functions
on lists does not in general give rise to total functions and some
care must be used to make sure your program will terminate.   We will
have more to say about proving termination in Chapter \chapref{PROVIN}.

\section{Simple S-expression recursion.}
\sectlab{sexprec}

	In the case of recursion on the structure of S-expressions,
the simplest situation is when the value of the function is
immediate for atoms, and for non-atoms depends only on the
values for the a-part and the d-part of the argument.  Thus /subst\//
was defined by
\beginfundef
\funlab{fcnsubst}
\vbox{
\hbox{\hskip0\unit $/subst/[/x/, /y/, /z\//] ← $}
\hbox{\hskip4\unit $    \qif  \qat /z/ \qthen  [\qif  /y/ \qeq /z/ \qthen 
 /x/ \qelse  /z\//]$}
\hbox{\hskip4\unit $    \qelse  /subst/[/x/, /y/, \qa /z\//] \qcons  /subst/[/x/, 
/y/, \qd /z\//]$}
}
\endfundef

More generally we have recursive definitions of the form
\beginfundef
\funlab{eqnspr1}
\vbox{
\hbox{\hskip0\unit $/f/ /x/ ← \qif  \qat /x/ \qthen  /g/ /x/ \qelse  
/h/[\qa /x/, \qd /x/, /f/ \qa /x/, /f/ \qd /x\//]$}
}
\endfundef

Here again the recursive definition of functions parallels the description
of the domain. 
The definitions of /size\// (the number of atoms in an S-expression) and /fringe\//
\beginfundef
\funlab{fcnsize}
\vbox{
\hbox{\hskip0\unit $/size/ /x/ ← \qif  \qat /x/ \qthen  1 \qelse  /size/ 
\qa /x/ + /size/ \qd /x/$}
}
\endfundef
\beginfundef
\funlab{fcnfringe}
\vbox{
\hbox{\hskip0\unit $/fringe/ /x/ ← \qif  \qat /x/ \qthen  </x/> \qelse 
 /fringe/ \qa /x/ * /fringe/ \qd /x/$}
}
\endfundef
are further examples of this form of definition.

	The S-expression analogue of (\funref{pr3}) and (\funref{pr3}) 
(primitive S-expression recursion) is 
\beginlisp
(DEFUN F(X Y)
  (COND ((ATOM X) (G X Y))
	(T (H (CAR X) (CDR X) Y (F (CAR X)(JA X Y)) (F (CDR X)(JD X Y))))))
(bb tex '(f))
\endlisp
\beginfundef
\funlab{eqnspr3}
\vbox{
\hbox{\hskip0\unit $/f\//[/x\//, /y\//] ← $}
\hbox{\hskip4\unit $    \qif  \qat /x\// \qthen  /g\//[/x\//, /y\//]$}
\hbox{\hskip4\unit $    \qelse  /h\//[\qa /x\//, \qd /x\//, /y\//, /f\//[\qa 
/x\//, /ja\//[/x\//, /y\//]], /f\//[\qd /x\//, /jd\//[/x\//, /y\//]]]$}
}
\endfundef
and the following definition of /equal\// is of this form
\beginlisp
(DEFUN EQUAL (X Y)
  (COND ((ATOM X) (COND ((ATOM Y) (EQ X Y)) (T NIL)))
	((ATOM Y) NIL)
	(T (AND (EQUAL (CAR X) (CAR Y)) (EQUAL (CDR X) (CDR Y))))))
(bb tex '(equal))
\endlisp
\beginfundef
\funlab{fcnequal}
\vbox{
\hbox{\hskip0\unit $/equal\//[/x\//, /y\//] ← $}
\hbox{\hskip4\unit $    \qif  \qat /x\// \qthen  [\qif  \qat /y\// \qthen 
 /x\// \qeq /y\// \qelse  \qNIL ]$}
\hbox{\hskip4\unit $    \qelsif  \qat /y\// \qthen  \qNIL $}
\hbox{\hskip4\unit $    \qelse  \qa /x\// \qequal \qa /y\// \qand \qd /x\// 
\qequal \qd /y\//$}
}
\endfundef

Note that using the fact that \qeq\ is in fact defined on non-atoms in
actual LISP implementations and properties of the propositional functions,
we can simplify the definition of /equal\// to 
\beginlisp
(bb tex '(equal))
\endlisp
\beginfundef
\vbox{
\hbox{\hskip0\unit $/equal/[/x/, /y\//] ← /x/ \qeq /y/ \qor  [\qnot \qat 
/x/ \qand \qnot \qat /y/ \qand \qa /x/ \qequal \qa /y/ \qand \qd /x/ \qequal 
\qd /y\//]$}
}
\endfundef
as was given in Chapter \chapref{READIN}.

	Although the above definition of /equal\// is an instance of the schema
\funref{spr3} it is more natural to think of it as a parallel recursion through
the two arguments rather than thinking of one of them as a parameter.  This
could of course be elaborated to carry along parameters as well as recurring
in parallel through some collection of arguments. 
In later chapters we will see more examples of programs that recur on more
than one argument.  (For example the  /samefringe\// program discussed in
Chapter \chapref{PROVEX}).  
The important point to check in such programs is that the collection 
of arguments being recurred on is always ``simpler'' in recursive calls
to the program being defined.

	The definition of /flatten\// is an example of a double recursion.
\beginlisp
(bb tex '(flatten flat))
\endlisp
\beginfundef
\funlab{fcnflatten}\vbox{
\hbox{\hskip0\unit $/flatten/ /x/ ← /flat/[/x/, \qNIL ]$}
\medskip
\hbox{\hskip0\unit $/flat/[/x/, /u\//] ← $}
\hbox{\hskip4\unit $    \qif  \qat /x/ \qthen  /x/ \qcons  /u/ \qelse  
/flat/[\qa /x/, /flat/[\qd /x/, /u\//]]$}
}
\endfundef

Although /flatten\// computes the same function as /fringe\//, it
is more efficient  because the /append\// operation used by /fringe\//
copies unnecessarily.   As we shall see in a later chapter,
/flatten\// is also an improvement over /fringe\// in that it is partially 
amenable to tail recursive evaluation.   
The kind of double recursion used in /flatten\// is often useful. 
One way of thinking of this form of recursion is that results are
computed from one side of the S-expression (the \qd\ side in this case) and then
passed along to the other side.  Thus we obtain a flow of information
from side to side as well as top to bottom.
The technique of writing a simple and easily understandable recursive definition
and then later optimizing by the kind of transformation made in going from
/fringe\// to /flatten\// is often useful.  

	Note that the definition of /flat\// does not fit the general
primitive recursive schema \funref{spr3}. 
Thus we have an example where one definition of a function clearly fits 
one of the simple recursion schemas and thus defines a total function, while
for another definition of the function this fact is not immediate.  Of
course showing that both definitions compute the same function also requires
some work.   We could add to our list of schemas some which
allow multiple recursions such as exhibited by /flatten/.  
However no matter how many such forms for defining total functions we allow,
we will eventually have to resort to the general form \funref{prec} which
is also the general form for S-expression recursion.
\section{Other structural recursions.}
\sectlab{strucrec}
	When S-expressions are used to represent a class of
expressions that are defined inductively then functions of these
expressions often have a recursive form closely related to the 
inductive definition of the expressions.  For example the
arithmetic interpreter /numval\// (\funref{numval}) computes directly
the value for constants and variables and for sums and products
it computes the value in terms of the values 
of the subexpressions from which the sum or product is constructd.  
The function /diff\// (\funref{diff}) which symbolically
differentiates the same class of expressions has a similar recursive
structure in that it knows the answers immediately for constants
and variables and for sums and products it uses the results for
subexpressions to obtain the final answer.  If we consider the arithmetic
expressions where sum and product are simple binary operators we can
write a simple recursion schema as follows:
\beginlisp
(DEFUN F (X Y)
    (COND ((NUM X) (GNUM X Y))
	  ((ISVAR X) (GVAR X Y))
	  ((ISSUM X) (GSUM (S1 X) (S2 X) Y (F (S1 X) Y) (F (S2 X) Y)))
	  ((ISPROD X) (GPROD (P1 X) (P2 X) Y (F (P1 X) Y) (F (P2 X) Y)))))
(bb tex '(f))
\endlisp
\beginfundef
\funlab{eqngpr1}
\vbox{
\hbox{\hskip0\unit $/f\//[/x\//, /y\//] ← $}
\hbox{\hskip4\unit $    \qif  /num\// /x\// \qthen  /gnum\//[/x\//, /y\//]$}
\hbox{\hskip4\unit $    \qelsif  /isvar\// /x\// \qthen  /gvar\//[/x\//, 
/y\//]$}
\hbox{\hskip4\unit $    \qelsif  /issum\// /x\// \qthen  /gsum\//[/s1\// 
/x\//, /s2\// /x\//, /y\//, /f\//[/s1\// /x\//, /y\//], /f\//[/s2\// /x\//, 
/y\//]]$}
\hbox{\hskip4\unit $    \qelsif  /isprod\// /x\// \qthen  /gprod\//[/p1\// 
/x\//, /p2\// /x\//, /y\//, /f\//[/p1\// /x\//, /y\//], /f\//[/p2\// /x\//, 
/y\//]]$}
}
\endfundef

Then the evaluation function /numval/
\beginlisp
(bb tex '(nval))
\endlisp\beginfundef
\funlab{fcnnumval}
\vbox{
\hbox{\hskip0\unit $/numval/[/e/, /a\//] ← $}
\hbox{\hskip4\unit $    \qif  /isnum/ /e/ \qthen  /cval/ /e/$}
\hbox{\hskip4\unit $    \qelsif  /isvar/ /e/ \qthen  /lookup/[/e/, /a\//]$}
\hbox{\hskip4\unit $    \qelsif  /issum/ /e/ \qthen  $}
\hbox{\hskip8\unit $        /sum/[/numval/[/s1/ /e/, /a\//], /numval/[/s2/ 
/e/, /a\//]]$}
\hbox{\hskip4\unit $    \qelsif  /isprod/ /e/ \qthen  $}
\hbox{\hskip8\unit $        /prod/[/numval/[/s1/ /e/, /a\//], /numval/[/s2/ 
/e/, /a\//]]$}
}
\endfundef
is an instance of this schema where /cval/, /lookup/, /sum\// and /prod\// 
are given.

	A more complicated example of
an interpreter with recursive structure based on the expression
language structure is the LISP interpreter /eval\// (\funref{evall}).

	In general if we have a domain defined by starting with
a base set (with computable test for membership) and a collection of
constructors with which we build elements of the domain by
repeated application starting with elements of the base set,
then there is a corresponding schema for recursive definition of 
functions on this domain.   We will see more examples and have 
more to say about this in later chapters.